package problem50;

//50.快速幂
//https://leetcode.cn/problems/powx-n/

class Solution {
    public double myPow(double x, long n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n < 0) return myPow(1/x, -n);

        if(n % 2 == 1) {
            double k = myPow(x, n/2);
            return x * k * k;
        }else {
            double k = myPow(x, n/2);
            return k * k;
        }
    }
}